package person.bing.fbcloud.leetcode;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 *
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
 * 找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。
 * 假定每组输入只存在唯一答案。
 * @author: mengfanbing
 * @date: 2020/7/22 10:38
 */
public class Q16 {
    public static void main(String[] args) {
        int[] nums = {0,2,1,-3};
        int target = 1;
        int i = threeSumClosest(nums, target);
        System.out.println(i);
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = nums[0] + nums[1] + nums[2];
        int diff = target - ans;
        diff = diff > 0 ? diff : -diff;
        int length = nums.length;
        for(int i=0;i<length-2;i++){
            int a = i+1;
            int b = length-1;
            while(a<b){
                int temp = nums[i] + nums[a] + nums[b];
                int realDiff = temp - target;
                int tempDiff = realDiff >= 0 ? realDiff : -realDiff;
                if(temp == target){
                    return temp;
                }
                if(tempDiff < diff){
                    ans = temp;
                    diff = tempDiff;
                }
                if(realDiff > 0){
                    b--;
                }else{
                    a++;
                }
            }
        }
        return ans;
    }
}
